Data partitioning is often used to improve computer performance when processing queries that involve large data sets having numerous data records, particularly in systems where an entire partition must be retrieved even in response to a query whose predicates might have filtered out most of the records of the partition. Such partitioning may be performed by selecting a data record attribute that is most commonly queried, such as price in a data set of items for sale, and then partitioning the data set into two partitions of equal size at the median value for the selected attribute, where each partition includes those data records whose value for the selected attribute is either below or above the median value, but not both. A partition may be further partitioned in this manner, typically until a predefined partition size requirement is met. By associating each partition with metadata indicating, for instance, the minimum and maximum value of the selected attribute, a query that involves the selected attribute can be evaluated using the metadata to determine the partitions that may be safely skipped (i.e., not retrieved from computer memory or other data storage device for further evaluation) by the computer when processing the query.